/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class MagicSquaresInGrid {
	public int numMagicSquaresInside(int[][] grid) {
		int n = grid.length;
		int res = 0;
		for (int i = 0; i < n - 2; i++) {
			for (int j = 0; j < n - 2; j++) {
				if (isMagic(grid, i, j)) {
					res++;
				}
			}
		}
		return res;
	}

	private boolean isMagic(int[][] grid, int i, int j) {
		int x = i, y = j;
		int xe = x + 3, ye = y + 3;
		// 检查对角
		int sum = 0;
		for (int k = 0; k < 3; k++) {
			sum += grid[x + k][y + k];
		}
		if (sum != 15) {
			return false;
		}
		sum = 0;
		for (int k = 0; k < 3; k++) {
			sum += grid[x + k][y + 2 - k];
		}
		if (sum != 15) {
			return false;
		}
		// 检查同一列
		for (int k = y; k < ye; k++) {
			if (grid[x][k] > 9 || grid[x][k] == 0 || grid[x + 1][k] > 9 || grid[x + 1][k] == 0 || grid[x + 2][k] > 9
					|| grid[x + 2][k] == 0)
				return false;
			if (grid[x][k] + grid[x + 1][k] + grid[x + 2][k] != 15) {
				return false;
			}
		}
		// 检查三行
		for (int k = x; k < xe; k++) {
			if (grid[k][y] + grid[k][y + 1] + grid[k][y + 2] != 15) {
				return false;
			}
		}
		return true;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] grid = { { 1, 8, 6 }, { 10, 5, 0 }, { 4, 2, 9 } }; // { { 4, 3, 8, 4 }, { 9, 5, 1, 9 }, { 2, 7, 6, 2 }
																	// };
		System.out.println(new MagicSquaresInGrid().numMagicSquaresInside(grid));
	}

}
